package basic.study.algorithms.solution.DynamicProgramming;

/**
 * @author Kevin
 * @date 2020/4/24 12:
 * 题目：几年教师节活动中，公司里为培训讲师提供了不同面值的饮料兑换券（每种面值数量不限），培训讲师可以领取兑换券去食堂兑换鲜榨果汁，要求兑换券和果汁必须等价，姜小虎想要兑换一杯果汁，计算它最少要领取几张兑换券，如果无法兑换返回-1.
 *
 * 输入描述：第一行：兑换券的面值种类（种类>0） 第二行：数组，代表兑换券面值（面值>0） 第三行：一个整数，代表饮料的价值（饮料的价值>0）
 *
 * 输出描述：对于每个测试用例，要求输出最少兑换券张数
 * ————————————————
 * 版权声明：本文为CSDN博主「爽儿-歪歪」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
 * 原文链接：https://blog.csdn.net/sinat_36059653/article/details/78110158
 */
import java.util.Scanner;
/**
 * 动态规划
 * @author Rose
 *
 */
public class minCoins2 {
    static int[] dp;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        //面值种类
        int n = in.nextInt();
        int[] money = new int[n];

        for (int i = 0; i < n; i++) {
            money[i] = in.nextInt();
        }
        //饮料价值
        int value = in.nextInt();
        dp = new int[value+1];
        getMinCount(money, value, 0);
        if(dp[value] == Integer.MAX_VALUE - 1)  //第一处：无法兑换
            System.out.println(-1);
        else
            System.out.println(dp[value]);//可以兑换
    }
    private static int min(int a, int b){
        return a>b?b:a;
    }
    private static void getMinCount(int[] money, int value, int i){
        if(i <= value){//第二处：边界限制
            if(i == 0){//第三处：当i = 0
                dp[i] = 0;
                getMinCount(money, value, i+1);
                return;
            }else{
                int min = Integer.MAX_VALUE - 1;
                for (int j = 0; j < money.length; j++) {
                    if(i >= money[j])
                        min = min(dp[i-money[j]] + 1, min);
                }
                dp[i] = min;
                if(i == value)
                    return;
                else
                    getMinCount(money, value, i+1);

            }
        }

    }
}

